{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b685c220",
   "metadata": {},
   "source": [
    "## 快速排序\n",
    "评判一个软件工程师的专业水平，一个重要的标准就是看他能否准确地对快速排序算法进行编码实现。只要不能熟练地将快速排序算法付诸实践，那么无论从事软件开发行业多少年，都不能用“专业”来形容。\n",
    "\n",
    "### 算法设计思路\n",
    "1. 随机选取元素 - pivot\n",
    "2. 对数组进行切割划分\n",
    "3. 元素调度是快速排序算法的核心\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "532b1a18",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 19, 21]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "def arrange_array_by_pivot(array, pivot):\n",
    "    \"\"\" 将数组分为3部分， 第1部分元素小于pivot, 第二部分元素等于pivot，第三部分元素大于pivot \"\"\"\n",
    "    i = 0\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] < pivot:\n",
    "            i += 1\n",
    "        elif array[i] >= pivot:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] < pivot:\n",
    "        i += 1\n",
    "    \n",
    "    k = i\n",
    "    S1 = array[0:i]\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] == pivot:\n",
    "            i += 1\n",
    "        else:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "    if array[i] == pivot:\n",
    "        i += 1\n",
    "    \n",
    "    S2 = array[k:i]\n",
    "    S3 = array[i:]\n",
    "\n",
    "    return S1, S2, S3\n",
    "    \n",
    "\n",
    "def selection(array, k):\n",
    "    \"\"\" 查找数组中第k小的元素 \"\"\"\n",
    "    if len(array) <= 1:\n",
    "        return array[0]\n",
    "    if k > len(array):\n",
    "        raise Exception('Out of range!')\n",
    "    \n",
    "    pivot = array[0]\n",
    "    is_good_pivot = False\n",
    "\n",
    "    while is_good_pivot != True:\n",
    "        pivot = random.choice(array)\n",
    "\n",
    "        S1, S2, S3 = arrange_array_by_pivot(array, pivot)\n",
    "        if len(S1) <= int((3/4)*len(array)) and len(S3) <= int((3/4)*len(array)):\n",
    "            is_good_pivot = True\n",
    "    \n",
    "    if len(S1) > 0 and k <= len(S1):\n",
    "        return selection(S1, k)\n",
    "    elif len(S2) > 0 and k <= len(S1) + len(S2):\n",
    "        return pivot\n",
    "    else:\n",
    "        return selection(S3, k - len(S1) - len(S2))\n",
    "    raise Exception('error')\n",
    "\n",
    "def partion(A, pivot):\n",
    "    i = 0\n",
    "    j = len(A) - 1\n",
    "    while i < j:\n",
    "        if A[i] > pivot:\n",
    "            temp = A[i]\n",
    "            A[i] = A[j]\n",
    "            A[j] = temp\n",
    "            j -= 1\n",
    "        else:\n",
    "            i += 1\n",
    "    if A[i] > pivot:\n",
    "        i -= 1\n",
    "    return i\n",
    "\n",
    "def quick_sort(A):\n",
    "    if len(A) == 0:\n",
    "        return []\n",
    "    if len(A) == 1:\n",
    "        return A\n",
    "    pivot = selection(A, int(len(A)/2)) # 选择中位数作为划分的依据\n",
    "    mark = partion(A, pivot)\n",
    "    first_part = quick_sort(A[0 : mark + 1])\n",
    "    second_part = quick_sort(A[mark + 1 : ])\n",
    "    first_part.extend(second_part)\n",
    "    return first_part\n",
    "\n",
    "A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]\n",
    "A = quick_sort(A)\n",
    "print(A)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80c89460",
   "metadata": {},
   "source": [
    "## 优化\n",
    "上面给出的算法内部存在两个递归调用的过程：\n",
    "1. 寻找中位数的算法\n",
    "2. 快速排序调用函数进行执行过程\n",
    "3. 使用循环来替代递归 - 尾部递归优化方案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1c9621ea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 19, 21]\n"
     ]
    }
   ],
   "source": [
    "## 尾部递归调用实现快速排序\n",
    "\n",
    "def partion_for_tail(A, begin, end, pivot):\n",
    "    i = begin\n",
    "    j = end\n",
    "    while i < j:\n",
    "        if A[i] > pivot:\n",
    "            temp = A[i]\n",
    "            A[i] = A[j]\n",
    "            A[j] = temp\n",
    "            j -= 1\n",
    "        else:\n",
    "            i += 1\n",
    "    if A[i] > pivot:\n",
    "        i -= 1\n",
    "    return i\n",
    "\n",
    "def tail_recursive_quicksort(A, begin, end):\n",
    "    while begin < end:\n",
    "        pivot = selection(A[begin:end+1], int((end - begin)/2))\n",
    "        mark = partion_for_tail(A, begin, end, pivot)\n",
    "        tail_recursive_quicksort(A, begin, mark)    # 递归调用\n",
    "        begin = mark + 1\n",
    "    return A\n",
    "\n",
    "A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]\n",
    "A = tail_recursive_quicksort(A, 0, len(A) - 1)\n",
    "print(A)\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
